﻿//#define CHECK

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;
using alib.Debugging;

using alib.Hashing;
using alib.Enumerable;
using alib.Collections;
using alib.Array;

namespace alib.dg
{
	using String = System.String;
	using Enumerable = System.Linq.Enumerable;
	using Array = System.Array;

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// 
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public partial class rw_graph : dg, IEditGraph
	{
		delegate void λEdge(int ix, ref Edge e);
		delegate void λG_Edge(rw_graph g, int ix, ref Edge e);
		delegate void λVertex(ref Vertex v);
		delegate int int_λVertex(ref Vertex v);
		delegate int int_λEdge(int ix, ref Edge e);
		delegate void λarr_int_Edge(Edge[] ea, int ix, ref Edge e);
		delegate void λG_3Edge(rw_graph g, ref Edge e1, int ix, ref Edge e2, ref Edge e3);
		delegate void λG_2Edge(rw_graph g, int ix1, ref Edge e1, int ix2, ref Edge e2);

		public rw_graph(Edge[] E, Vertex[] V)
			: base(E, V)
		{
			_create_freelists();
		}
		public rw_graph()
		{
			_create_freelists();
		}

		public rw_graph(IGraph ig)
			: base((dg)ig)
		{
			rw_graph rwg;

			if ((rwg = ig as rw_graph) != null)
			{
				this.vertex_freelist = rwg.vertex_freelist;
				this.edge_freelists = rwg.edge_freelists;
				this.c_blocks_free = rwg.c_blocks_free;
			}
			else
			{
				_create_freelists();
			}
		}

		public enum GraphEditOp
		{
			AddedVertex,
			AddedEdge,
			DeletedEdge,
			DeletedAllEdges,
			DeletedVertex,
			ClearedGraph,
			Unknown,
		};

		protected void RaiseEvent(GraphEditOp op, int data = default(int))
		{
			var _tmp = GraphChangedEvent;
			if (_tmp != null)
				_tmp(op, data);
		}

		public event Action<GraphEditOp, int> GraphChangedEvent;

		public void clear_graph()
		{
			_create_freelists();
#if CHECK
			check();
#endif
			RaiseEvent(GraphEditOp.ClearedGraph);
		}

		static void AllocateNew<T>(ref T[] arr, ref int _max, int req)
			where T : struct
		{
			int _new = _max + req, _cap = arr.Length;
			if (_new > _cap)
			{
				_cap <<= 1;
				if (_cap < _new)
					_cap = _new;

				//Debug.Print("realloc {0} table, capacity {1} -> {2}",
				//	arr.GetType().GetElementType().Name,
				//	arr.Length,
				//	_cap);

				var _newarr = new T[_cap];
				if (_max > 0)
					Array.Copy(arr, 0, _newarr, 0, _max);
				arr = _newarr;
			}
			_max = _new;
		}

		public Vref add_vertex(int value)
		{
			Vref vr;
			if (c_vertex_free > 0)
			{
				Debug.Assert(vertex_freelist >= 0 && vertex_freelist < VertexAlloc);
				vr = new Vref(vertex_freelist);
				c_vertex_free--;
				vertex_freelist = V[vr].nxt;
			}
			else
			{
				vr = new Vref(c_vertex_max);
				AllocateNew(ref V, ref c_vertex_max, 1);
			}

			V[vr] = new Vertex
			{
				e_in = Eref.None,
				e_out = Eref.NotValid,
				c_out = 0,
				value = value,
			};

#if CHECK
			check();
#endif
			RaiseEvent(GraphEditOp.AddedVertex, vr);
			return vr;
		}

		void delete_vertex(Vref vr, ref Vertex v)
		{
			if (v.IsFree)
				throw new Exception("The vertex is already free");
			if (v.c_out > 0 || v.e_in != Eref.None)
				throw new Exception("Remove all edges before deleting a vertex");

			v.value = 0;
			v.status = status.free;
			v.prv = Vref.NotValid;
			v.nxt = vertex_freelist;

			vertex_freelist = vr;
			c_vertex_free++;
		}

		public void delete_vertex(Vref vr)
		{
			if (vr < 0 || vr >= VertexAlloc)
				throw new GraphException("The vertex is not valid");

			delete_vertex(vr, ref V[vr]);
#if CHECK
			check();
#endif
			RaiseEvent(GraphEditOp.DeletedVertex, vr);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Eref create_edge(Vref v_from, Vref v_to, int value)
		{
			if (!vertex_is_valid(v_from))
				throw new GraphException("The 'from' vertex is not valid");

			if (!vertex_is_valid(v_to))
				throw new GraphException("The 'to' vertex is not valid");

			if (v_from == v_to)
				throw new GraphException("Cannot add self-edge to the graph");

			if (vertex_has_ancestor(v_to, v_from))
				throw new GraphException("Cannot create a cycle in the graph");

			Edge enew = new Edge
			{
				v_from = v_from,
				v_to = v_to,
				status = status.NotValid,
				value = value
			};

			Eref er;
			if ((er = try_reuse_edge(ref enew, ref V[v_from])) < 0)
				er = add_new_edge(ref enew, ref V[v_from]);

#if CHECK
			check();
#endif
			RaiseEvent(GraphEditOp.AddedEdge, er);
			return er;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		Eref try_reuse_edge(ref Edge _new, ref Vertex vfrom)
		{
			Eref ix = vfrom.e_out + vfrom.c_out;

			if (!is_freelist_entry(ix))
				return Eref.NotValid;

			reclaim_freelist_edges(ix, ref E[ix], 1);

			vfrom.c_out++;

			_new.e_next = ix;
			E[ix] = _new;
			insert_peer_edge(ref E[ix].e_next, ref V[_new.v_to].e_in);

			return ix;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		Eref alloc_edges(int c)
		{
			Debug.Assert(c > 0);

			Eref er;
			if ((er = try_freelist_alloc(c)) < 0)
			{
				er = new Eref(c_edge_max);
				AllocateNew(ref E, ref c_edge_max, c);
			}
#if TIDY_ALLOC
			dbg_initialize_allocation(er, c);
#endif
			return er;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		Eref add_new_edge(ref Edge _new, ref Vertex vfrom)
		{
			var rsrc = vfrom.OutEdgeRange;
			var edst = vfrom.e_out = alloc_edges(vfrom.c_out = rsrc.c + 1);

			Eref enew = _new.e_next = edst + rsrc.c;
			E[enew] = _new;

			insert_peer_edge(ref E[enew].e_next, ref V[_new.v_to].e_in);

			if (rsrc.c > 0)
			{
				shift_out_edges(rsrc, edst);

				free_edges(rsrc);
			}
			return enew;
		}

		/// new edge peer loop status: if it is the first (only) edge for
		/// the vertex, then it is the master for the target vertex and that
		/// vertex's 'e_in' value is the post-shift (updated) value. But
		/// even though this would make the vertex 'seen,' it doesn't need
		/// to be listed as 'seen' because it is impossible for another visit to
		/// be attempted. if it there are additional edges for the vertex, the
		/// vertex's master edge is not changed, and it will have a valid loop
		/// which may need updating if it has any duplicate-source edges so
		/// it should not be marked 'seen'
		void insert_peer_edge(ref Eref _new_nxt, ref Eref _vto_ein)
		{
			if (_vto_ein < 0)
				_vto_ein = _new_nxt;
			else
				_new_nxt = swap(_new_nxt, ref E[_vto_ein].e_next);
		}

		static Eref swap(Eref _new_nxt, ref Eref _ein_nxt)
		{
			var _tmp = _ein_nxt;
			_ein_nxt = _new_nxt;
			return _tmp;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		struct EdgeRangeDelta
		{
			public EdgeRangeDelta(EdgeRange _src, int delta)
			{
				this._src = _src;
				this.delta = delta;
			}
			public EdgeRange _src;
			public int delta;

			public Eref shift_check(ref Eref _nxt, out Eref _old)
			{
				if (_src.Contains(_old = _nxt))
					_nxt += delta;
				return _nxt;
			}
		};

		/// perilous: it is not just a matter of directly and independently updating each out-edge's 
		/// presence in its peer loop as the out-group is being relocated, because multiple edges 
		/// between the same two verticies are also peers to each other. instead, for all loops of 
		/// each targeted vertex, update all edge index values which are 'out of range' by modifying 
		/// their loop links, while at the same time traversing that loop (via the old values). the 
		/// loop may become temporarily corrupt in our wake, so be sure to use an updated value to 
		/// detect termination. furthermore, the 'out of range' method is insufficient when the 
		/// source and target ranges of the overlap, unless each we make sure never to update each
		/// target vertex only once

		unsafe void shift_out_edges(EdgeRange rsrc, Eref edst)
		{
			Array.Copy(E, rsrc.ix, E, edst, rsrc.c);

			var erd = new EdgeRangeDelta(rsrc, edst - rsrc.ix);

			Vref* seen = stackalloc Vref[rsrc.c];
			int c_seen = 0;

			Eref e;
			for (e = edst; e < edst + rsrc.c; e++)
			{
				Vref vt = E[e].v_to;
				for (int j = 0; j < c_seen; j++)
					if (seen[j] == vt)
						goto already_done;

				seen[c_seen++] = vt;
				update_peer_loop(erd, ref V[vt].e_in);

			already_done:
				;
			}
		}

		void update_peer_loop(EdgeRangeDelta erd, ref Eref _vtx_ein)
		{
			Eref _start, _old, _cur = erd.shift_check(ref _vtx_ein, out _start);
			do
				_cur = erd.shift_check(ref E[_cur].e_next, out _old);
			while (_start != _old);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void delete_edge(Eref er)
		{
			if (er < 0 || er >= EdgeAlloc)
				throw new GraphException("The edge is not valid");
			if (E[er].IsFree)
				throw new GraphException("The edge is already free");

			_remove_edge(er, ref E[er]);
#if CHECK
			check();
#endif
			RaiseEvent(GraphEditOp.DeletedEdge, er);
		}

		public void delete_all_in_edges(Vref vr)
		{
			if (!vertex_is_valid(vr))
				throw new GraphException("The vertex is not valid");

			Eref er = vertex_unary_parent(vr);
			if (er >= 0)
			{
				_remove_edge(er, ref E[er]);
			}
			else
			{
				var earr = vertex_in_edges(vr);
				Debug.Assert(earr.Length > 1 && earr.IsDistinct());

				Array.Sort(earr);

				for (int i = earr.Length - 1; i >= 0; i--)
				{
					var e = earr[i];
					_remove_edge(e, ref E[e]);
				}
			}
#if CHECK
			check();
#endif
			RaiseEvent(GraphEditOp.DeletedAllEdges, vr);
		}

		void _remove_edge(Eref er, ref Edge e)
		{
			if (e.e_next == er)
				V[e.v_to].e_in = Eref.None;
			else
				adjust_peer_list(ref V[e.v_to].e_in, er, e.e_next);

			remove_out_edge(ref V[e.v_from], er);
		}

		void adjust_peer_list(ref Eref _vto_ein, Eref _del, Eref _del_nxt)
		{
			if (_vto_ein == _del)
				_vto_ein = _del_nxt;

			E[edge_peer_list_prev(_del)].e_next = _del_nxt;
		}

		void remove_out_edge(ref Vertex vfrom, Eref e_dst)
		{
			Debug.Assert(vfrom.c_out > 0);

			int c = --vfrom.c_out;
			if (c == 0)
				vfrom.e_out = Eref.NotValid;
			else
			{
				var rsrc = new EdgeRange(e_dst + 1, c - ((int)e_dst - (int)vfrom.e_out));

				shift_out_edges(rsrc, e_dst);

				e_dst = rsrc.Last;
			}

			free_single_edge(e_dst);
		}

		[Conditional("DEBUG")]
		void dbg_initialize_allocation(int ix, int c)
		{
			for (int i = 0; i < c; i++, ix++)
				E[ix].reset(status.NotValid);
		}

		public override String ToString()
		{
			return String.Format("[V: count.{0} alloc.{1} free.{2}]  [E: count.{3} alloc.{4} free.{5} blks.{6}]",
				VertexCount,
				VertexAlloc,
				c_vertex_free,
				EdgeCount,
				EdgeAlloc,
				c_edge_free,
				c_blocks_free);
		}

#if !DEBUG
		public void check() { }
#endif
	};
}